IOI 96 (Veszprem, Ungaria)

Problema 2. Joc

Sa consideram urmatorul joc intre doi jucatori. Se pleaca de la o secventa
de numere intregi pozitive. Cei doi jucatori actioneaza alternativ. Cand ii
vine randul, un jucator alege un numar situat la marginea secventei
(stanga sau dreapta). Numarul selectat este sters din secventa. Jocul se
termina cand toate numerele au fost sterse. Primul jucator castiga daca suma
numerelor pe care le-a selectat este mai mare sau egala decat suma
numerelor selectate de al doilea jucator. Al doilea jucator joaca cat mai
bine posibil.

Primul jucator incepe jocul.

Se cunoaste ca, daca initial secventa contine un numar par de elemente,
atunci primul jucator are o strategie de castig.
Scrieti un program care implementeaza strategia de castig a primului jucator.
Raspunsul celui de al doilea jucator este asigurat de un program dat. Cei doi
jucatori comunica prin trei proceduri ale modulului Play, accesibil
programului. Aceste proceduri sunt StartGame, MyMove si YourMove. Primul
jucator incepe jocul executand procedura fara parametri StartGame. Daca primul
jucator selecteaza un numar din capatul stang al secventei, el executa
procedura MyMove('L'). Similar, prin executarea instructiunii MyMove('R'), el
trimite un mesaj catre al doilea jucator indicandu-i ca a selectat un numar
din capatul drept al secventei. Al doilea jucator (calculatorul) muta imediat
si primul jucator poate afla aceasta mutare executand instructiunea
YourMove(C) unde C este o variabila tip caracter. Valoarea lui C este 'L' sau
'R' dupa cum selectia elementului s-a facut din marginea stanga, respectiv
dreapta a secventei.

Intrare

Prima linie a fisierului INPUT.TXT contine numarul N de elemente din secventa.
N este par si 2=F3N=F3100. Celelalte N linii contin fiecare cate un numar,
reprezentand secventa de la stanga la dreapta.
Fiecare numar are valoarea maxim 200.

Iesire

 Cand jocul s-a sfarsit, programul va scrie rezultatul final al jocului in
 fisierul OUTPUT.TXT. Fisierul contine doua numere pe prima linie. Primul
 numar este suma elementelor selectate de primul jucator iar al doilea numar
 este suma elementelor selectate de al doilea jucator. Programul vostru
 trebuie sa joace un joc si iesirea trebuie sa corespunda acestuia.

Exemplu

Pentru fisierul INPUT.TXT:
6
4
7
2
9
5
2

un fisier OUTPUT.TXT posibil poate fi:
15 14

=======================================
Solutia 1 (Mihai Stroe)

    Ideea de rezolvare este urmatoarea: se calculeaza o matrice care pastreaza
  rezultatul pentru o subsecventa a sirului initial. Se porneste de la
  subsecvente de lungime 1, adica de la elementele sirului initial; in
  acele puncte, diferenta este exact -(valoarea elementelor), deoarece ultima
  mutare o face al doilea jucator.
     A[lung,i]= diferenta intr-un final de joc perfect cu tabla initiala de
             lungime lung si care incepe de pe pozitia i a sirului dat
     Daca sirul este de lungime para, muta primul jucator si se va calcula un
  maxim; in caz contrar se calculeaza un minim.

     a[lung,i]= --max(a[lung-1,i+1]+sir[i],a[lung-1,i]+sir[i+lung-1])
                \      daca muta primul jucator
                  \ min(a[lung-1,i+1]-sir[i],a[lung-1,i]-sir[i+lung-1])
                       daca muta al doilea jucator
     Rezultatul jocului este dat de A[n,1]. Programul functioneaza in timp
  util pentru orice date de intrare.
     Dupa aceasta prima rezolvare, care nu folosea unit-ul PLAY, am revenit
  asupra problemei si am implementat si partea de simulare a jocului; aceasta
  foloseste matricea deja generata. Desi se comunica cu unit-ul PLAY,
  programul nu genereaza TRACE FILE (???);

{$m 60000,0,10000}
uses play;
var a:array[1..100,1..100]of longint;
    sir:array[1..100]of longint;
    x,y,i,j,lung,k,l,m,n:longint;
    fi,fo:text;
    c:char;

function min(i,j:longint):longint;
begin
  if i<j then min:=i else min:=j;
end;

function max(i,j:longint):longint;
begin
  if i>j then max:=i else max:=j;
end;

begin
  assign(fi,'input.txt');
  reset(fi);
  readln(fi,n);
  for i:=1 to n do
      readln(fi,sir[i]);
  close(fi);
  for i:=1 to n do
      a[1,i]:=-sir[i];
  for lung:=2 to n do
      for i:=1 to n-lung+1 do
          if lung mod 2=0 then a[lung,i]:=max(a[lung-1,i+1]+sir[i],a[lung-1,i]+sir[i+lung-1])
                          else a[lung,i]:=min(a[lung-1,i+1]-sir[i],a[lung-1,i]-sir[i+lung-1]);
  m:=0;
  for i:=1 to n do
      m:=m+sir[i];
  assign(fo,'output.txt');
  rewrite(fo);
  writeln(fo,(m+a[n,1])div 2,' ',(m-a[n,1])div 2);
  close(fo);
  x:=1;y:=n;
  k:=0;l:=0;
  startgame;
  while x<y do
    begin
      if a[y-x,x+1]+sir[x]>a[y-x,x]+sir[y] then
         begin
           mymove('L');
           k:=k+sir[x];
           inc(x);
         end
         else
         begin
           mymove('R');
           k:=k+sir[y];
           dec(y);
         end;
      yourmove(c);
      if c='L'then
         begin
           l:=l+sir[x];
           inc(x);
         end
         else
         begin
           l:=l+sir[y];
           dec(y);
         end;
    end;
end.
-------------------------
